package leetcode.editor.cn;

public class _96_UniqueBinarySearchTrees {
    public static void main(String[] args) {
        Solution solution = new _96_UniqueBinarySearchTrees().new Solution();
        int i = solution.numTrees(3);
        System.out.println(i);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // 动态规划写的干净一点
    class Solution {
        public int numTrees(int n) {
            if (n == 0) return 0;
            int[][] dp = new int[n + 2][n + 2];
            for (int i = 0; i <= n + 1; i++) {
                for (int j = 0; j <= n + 1; j++) {
                    if (j <= i) {
                        dp[i][j] = 1;
                    }
                }
            }

            for (int i = n; i >= 1; i--) {
                for (int j = i + 1; j <= n; j++) {
                    for (int k = i; k <= j; k++) {
                        dp[i][j] += dp[i][k - 1] * dp[k + 1][j];
                    }
                }
            }
            return dp[1][n];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}